「03」递归 3

相关题目

例1. 奇怪的汉诺塔

奇怪的汉诺塔

汉诺塔问题，条件如下：

1、这里有 $A$、$B$、$C$ 和 $D$ 四座塔。

2、这里有 $n$ 个圆盘，$n$ 的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔 $A$ 上，且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔 $A$ 转移到塔 $D$ 上。

6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 $A$ 移动到塔 $D$ ，所需的最小移动次数是多少。

在三塔的汉诺塔问题中，假设有 $n$ 个圆盘，$A, B, C$ 3 个柱子，目标是把 $A$ 上的 $n$ 个圆盘借助柱 $B$ 移到 $C$ 上面去，我们会先移动 $A$ 柱上面的 $n - 1$ 个圆盘借助柱 $C$ 移到 $B$ 柱上，再把最大的圆盘移动到 $C$ 柱上，然后把 $B$ 柱上的 $n - 1$ 个圆盘借助柱 $A$ 移到 $C$ 上面。设 $f(n)$ 表示所需的最小操作数，那么前面的三次操作所需的最小操作数分别为 $f(n - 1)$, 1, $f(n - 1)$。因此我们有关系式：

$f(n) = f(n - 1) + 1 + f(n - 1) = 2f(n - 1) + 1$，其中边界 $f(0) = 0$

在本题中，我们有了两个用来中转的柱子，因此，我们可以考虑先移动一部分圆盘 $x$ 移到 $B$ 柱上，这有两个中转的柱子 $C、D$ 可供使用，然后在把 $A$ 上剩下的圆盘通过 $C$ 中转移到 $D$ 上，最后再把 $B$ 上的圆盘通过 $A、C$ 中转移到 $D$ 上。因此，如果我们用 $g(n)$ 表示通过两个柱子中转，移动 $n$ 个圆盘总共所需的最少移动步数，那么有关系式

$g(n) = \min \{ g(x) + f(n - x) + g(x) \}$，其中 $0 \le x < n$, $g(0) = 0$

参考代码

#include<bits/stdc++.h>
using namespace std;

int d[15], f[15];

int main() {
	for (int i = 1; i <= 12; i++) d[i] = 2 * d[i - 1] + 1;
	
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 1; i <= 12; i++) {
		for (int j = 0; j < i; j++) {
			f[i] = min(f[i], f[j] + d[i - j] + f[j]);
		}
	}
	
	for (int i = 1; i <= 12; i++) cout << f[i] << "\n";
} 

例2. 分形 Fractal

分形 Fractal

一级盒子分形：

X

二级盒子分形：

X X
 X
X X

如果用 $B(n - 1)$ 代表第 $n-1$ 级盒子分形，那么第 $n$ 级盒子分形即为：

B(n - 1)        B(n - 1)

       B(n - 1)

B(n - 1)        B(n - 1)

你的任务是绘制一个 $n$ 级的盒子分形。